/**
 * @param {number[]} nums
 * @return {number}
 */
// 原地hash，但是会修改原来的数组
var findDuplicate = function (nums) {
    for (let i = 0; i < nums.length; i++) {
        let n = Math.abs(nums[i]) - 1
        if (nums[n] < 0) return Math.abs(nums[i])
        else nums[n] = -nums[n]
    }
};
// 快慢指针
// 由于有n+1个数，并且每个数的大小为1~n，那么就可以假设每一项的值，是指向的位置
// 比如[1, 3, 4, 2, 2]，3指向第一个2的位置，存在多个重复的元素，所以一定有环
// 将数组看作链表，用快慢指针。索引为0的位置默认为头节点
var findDuplicate = function (nums) {
    let slow = 0
    let fast = 0
    while(true) {
        slow = nums[slow] // 走一步
        fast = nums[nums[fast]] // 走两步
        if(slow === fast) {
            fast = 0; // 回到头节点
            while(true) {
                if(slow === fast) return slow
                slow = nums[slow]
                fast = nums[fast]
            }
        }
    }
}